Федеральне агентство з освіти
Державна освітня установа вищої професійної освіти
Вятський державний гуманітарний університет
Математичний факультет
Кафедра алгебри і геометрії
Випускна кваліфікаційна робота
Зв'язок комбінаторики з різними розділами математики
Виконала:
студентка V курсу математичного факультету
Бородуліна Юлія Анатоліївна
Науковий керівник:
к. ф-м. н., доцент кафедри алгебри і геометрії
Є.М. Ковязіна
Рецензент:
к. ф-м. н., доцент кафедри алгебри і геометрії
О.С. Руденко
Допущена до захисту в державної атестаційної комісії
«___» __________2005 Р. Зав. кафедрою Є.М. Вечтомов
«___»___________ 2005 Декан факультету В.І. Варанкіна
Кіров
2005

Зміст

Введення ................................................. .................................................. ........ 3
§ 1. Застосування леми Бернсайда до рішення комбінаторних завдань ......... 5
1.1. Орбіти групи перестановок ............................................... ........... 5
1.2. Довжина орбіти групи перестановок. Лемма Бернсайда ................ 5
1.3. Комбінаторні задачі ................................................ .................... 8
§ 2. «Метод просіювання ».............................................. ................................ 21
2.1. Формула включення і виключення .............................................. .. 21
2.2. Загальний «метод просіювання» або «пропускання через решето». Решето Сільва-Сильвестра .............................................. .................................................. ..... 23
2.3. Використання загального методу решета в теорії чисел ................. 23
§ 3. Розбиття фігур на частини меншого діаметру ...................................... 28
§ 4. «Щасливі квитки ».............................................. ................................ 34
Бібліографічний список ................................................ ........................... 39

Введення

Область математики, в якій вивчаються питання про те, скільки різних комбінацій, підлеглих тим чи іншим умовам, можна скласти з заданих об'єктів називається комбінаторика. Комбінаторика виникла в XVI столітті. Питання, що стосуються азартних ігор, з'явилися рушійною силою у розвитку комбінаторики. Зараз комбінаторні методи застосовуються як в самій математиці, так і поза нею - теорія кодування, планування експерименту, топологія, кінцева алгебра, математична логіка, теорія ігор, кристалографія, біологія, статистична фізика, економіка і т.д.
Комбінаторика, пройшовши багатовіковий шлях розвитку, знайшовши власні методи дослідження, з одного боку, широко використовується при вирішенні задач алгебри, геометрії, аналізу, з іншого боку, сама використовує геометричні, аналітичні та алгебраїчні методи дослідження.
Мета дипломної роботи: показати зв'язок комбінаторики з різними розділами математики.
Завдання:
1. Вивчити лему Бернсайда і вирішити комбінаторні задачі про розфарбовування з її застосуванням;
2. Показати застосування методу «просіювання» для підрахунку кількості простих і взаємно простих чисел;
3. Розглянути теорему Борсука, яка вирішує завдання для плоских фігур про розбивку їх на частини меншого діаметру;
4. Вирішити задачу про «щасливих квитках».
Дипломна робота складається з чотирьох частин:
У § 1 розглянуто зв'язок теорії груп з комбінаторикою: застосування групи перестановок до рішення комбінаторних завдань. Основний використовуваний факт у цьому параграфі - лема Бернсайда.
У § 2 показаний найбільш загальний метод перерахунку (відомий ще в XVIII столітті), а також наведено приклади його використання в теорії чисел.
Параграф 3 присвячений питанню комбінаторної геометрії - питання про розбивку фігури на кілька менших частин. Розглянута теорема Борсука є тим стрижнем, навколо якого можливе подальший розгляд цього питання.
У § 4 вирішується відома завдання про щасливі квитках із залученням методів з математичного аналізу.

§ 1. Застосування леми Бернсайда до рішення комбінаторних завдань [3]

1.1. Орбіти групи перестановок
Нехай G - група перестановок на безлічі М = {1, 2, ..., n}. Підмножина Про М називається орбітою групи G, якщо: а) α (a) O для будь-якого α G і будь-якого a O, тобто дію перестановок з G на елементи Про не виводить за межі О; б) будь-які два елементи з О можна перевести один в одного деякою перестановкою з G.
Легко показати, що будь-яка група перестановок G = {ε = α _0, α _1, ..., α _{k -1}} має орбіти.
Орбітами подібного виду вичерпуються всі типи орбіт, тобто, якщо О - орбіта групи G і а О, то О = О (а).
Будь-які дві орбіти О (а) і О (b) або збігаються (якщо b O (a)), або не перетинаються (якщо b O (a)).
Таким чином, безліч М розпадається в об'єднання непересічних підмножин - орбіт групи G. У зв'язку з розбивкою безлічі М на орбіти групи перестановок G виникають наступні два питання:
1) Скільки орбіт має група G на множині М?
2) Яка довжина кожної з цих орбіт, тобто зі скількох елементів вони полягають?
Відповімо на ці питання.
1.2. Довжина орбіти групи перестановок. Лемма Бернсайда
Відповімо на друге питання. Для будь-якого елемента а М можна розглянути групу G _a всіх перестановок з G, для яких точка а є нерухомою. Вона називається стабілізатором точки а. Відповімо на питання, довівши наступну теорему:
Довжина орбіти О (а) дорівнює індексу стабілізатора G _a в групі G, тобто | O (a) | = | G |: | G _a |.
Доказ. Нехай G = {ε = α _0, α _1, ..., α _{k -1},} G _a = {ε = β _0, β _1, ..., β _{s -1}.} Для підрахунку різних елементів у послідовності a = α ₀ (a), α ₁ (a), ..., α _{k -1} (a) зручно особливим чином розташувати в ряд елементи групи G. Для цього використовуємо той факт, що групу G можна представити у вигляді об'єднання всіляких непересічних правих класів суміжності по підгрупі G _a, що мають однакове число елементів. Тобто існують перестановки γ ₀ = ε, γ _1, ..., γ _{l -1} з групи G такі, що всі перестановки ряду
α _{0 =} β ₀ ° γ ₀ = ε, α ₁ = β ₁ ° γ _0, ..., α _{s -1} = β _{s -1} ° γ _0,
α _{s =} β ₀ ° γ _1, α _{s +1} = β ₁ ° γ _1, ..., α _{2 s -1} = β _{s -1} ° γ _1, (*)
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
α _{(l-1) s =} β ₀ ° γ _l-1, α _{(l-1) s +1} = β ₁ ° γ _l-1, ..., α _ls-1 = β _s-1 ° γ _l-1
попарно різні і вичерпують всю групу G.
Для будь-якого i = 0, ..., l -1 застосування s перестановок α _is, α _{is +1,} ..., α _{(i +1) s -1,} що утворюють i-ту рядок таблиці (*), до елемента а дає один і той же елемент γ _i (а) (так як β _0, β _1, ..., β _{s -1} залишають а нерухомим). Всі l елементів γ _i (а) попарно різні. Дійсно, якщо б γ _i (а) = γ _j (а) для деяких i, j, то а = (γ _j ° γ _i ^-1) (a), тобто перестановка (γ _j ° γ _i ^-1) G _a. Але це можливо тільки тоді, коли γ _i і γ _j містяться в одному правому класі суміжності групи G за підгрупою G _a, чого бути не може. Таким чином, довжина орбіти О (а) дорівнює l, тобто кількістю рядків у таблиці (*): k = l ∙ s (тобто l є індексом підгрупи в групі). По теоремі Лагранжа l = | G |: | G _a |, тобто | O (a) | = | G |: | G _a |. Теорема доведена.
Тепер відповімо на перше питання. Для цього сформулюємо і доведемо лему Бернсайда.
Нехай λ (α) - число нерухомих точок перестановки α, t (G) - число орбіт групи перестановок G = {ε = α _0, α _1, ..., α _{k -1},} що діє на множині М = {1, 2, ..., n}. Тоді для будь-якої групи перестановок має місце рівність:
t (G) = λ (α), де α G.
Доказ. Розглянемо відношення «перестановка α зберігає нерухомим елемент m» між перестановками групи G і елементами множини М. Зіставимо парам (α, m), α G, m M, вершини прямокутної мережі і відзначимо ті з них, для яких відповідна пара (α, m) знаходиться у зазначеному відношенні, тобто α (m) = m (рис. 1).
Ін

α ₀ α ₁ α ₂ α _3. . . α _{k -1} G

Рис. 1

.
.
.

ими словами, побудуємо графік зазначеного відносини.
ref SHAPE \ * MERGEFORMAT
Число зазначених точок (точок, що належать графіком) можна підрахувати двома способами: визначити число зазначених точок на кожній вертикалі і підсумувати отримані величини або ж визначити число таких крапок на кожній горизонталі і обчислити їх суму. Згідно з визначенням відносини на кожній вертикалі зазначаються всі точки, які зберігаються перестановкою α, що відповідає цій вертикалі. Їх число дорівнює λ (α). Тому число всіх точок графіка одно
λ (α ₀₎ + λ (α ₁₎ + ... + λ (α _k-1) = λ (α), де α G.
З іншого боку, на кожній горизонталі зазначаються всі перестановки, що зберігають елемент m M, що відповідає цієї горизонталі. А такі перестановки утворюють групу G _m - стабілізатор елемента m, - і їх число, по теоремі, доведеною раніше, так само | G _m | = | G |: | O (m) |. Тому при другому способі підрахунку числа зазначених точок графіка розглянутого відносини отримуємо вираз | G ₁ | + | G ₂ | + ... + | G _n | = | G _m | (m M).
Однак, якщо елементи i, j M містяться в одній орбіті, то О (i) = O (j), і тому | G _i | = | G |: | O (i) | = | G |: | O (j) | = | G _j |. Нехай О _1, О _2, ..., Про _t - Все орбіти групи G такі, що

, І доданки в цьому об'єднанні не перетинаються. Розіб'ємо | G _m | (де m M) на частини так, щоб всередині кожної з цих частин підсумовування йшло за елементами деякої орбіти:
_m | = _m | + _m | + ... + _m |.
Кожне з t доданків в правій частині цієї рівності можна перетворити таким чином:

_m | =

= | G |.
Тому

_m | = | G | + ... + | G | = t ∙ | G |.
Таким чином, при другому способі підрахунку ми отримали t ∙ | G | зазначених точок графіка. Прирівнюючи величини, отримані при першому і другому способах, отримаємо
t | G | =

,
тобто t = t (G) =

.
Лема доведена.

1.3. Комбінаторні задачі

Розглянемо кілька прикладів, що ілюструють можливості застосування леми Бернсайда при вирішенні комбінаторних завдань на перерахування.
Завдання 1. Скількома способами можна розфарбувати вершини куба в три кольори (наприклад, червоний, синій і зелений)?
Рішення. (В інших завданнях будемо використовувати позначення, аналогічні позначенням в цьому завданні). Оскільки кожну з восьми вершин куба можна розфарбувати трьома способами, причому незалежно від того, як розфарбовані інші вершини, то безліч всіх вершин куба можна розфарбувати ^{8 березня} = 6561 різними способами (за формулою

). Однак при такому підході до вирішення завдання мовчазно передбачається, що ми вміємо розрізняти вершини куба перед забарвленням, тобто, скажімо, куб жорстко закріплений або його вершини занумеровані. При цьому отриманий відповідь можна інтерпретувати в такий спосіб: можна так розфарбувати ^{8 березня} абсолютно однакових, жорстко закріплених кубів, що всі вони будуть відрізнятися. Для 3 ⁸ +1 кубів цього зробити вже не можна. Ситуація істотно змінюється, якщо ми відмовимося від припущення про те, що куби жорстко закріплені, так як по-різному забарвлені куби можна повернути так, що в новому положенні їх забарвлення співпадуть (рис.2).

° - синій колір
• - червоний колір
* - Зелений колір
Рис. 2

Природно вважати, що два куби розфарбовані однаково, якщо їх розмальовки збігаються аж до способу розміщення кубів на просторі, тобто аж до деякого обертання одного з кубів. Будемо говорити, що такі розмальовки кубів геометрично можна відрізнити. Тому природним уточненням завдання про розфарбовування є наступне завдання: скількома геометрично різними способами можна розфарбувати вершини куба в три кольори.
Переформулюємо тепер цю задачу так, щоб стала зрозумілою її зв'язок з лемою Бернсайда. Нехай М - безліч всіляких по-різному розфарбованих кубів одного розміру, положення яких в просторі фіксована (| M | = 3 ^8), G - група всіх обертань куба. Група G природним чином визначає групу перестановок на безлічі М. Саме, якщо α G - деяке обертання, то кожному кубу з М можна зіставити деякий інший куб, який виходить з першого при обертанні α. Ця відповідність є перестановкою на М, яку будемо позначати

. Групу всіх таких перестановок множини М, що визначаються перестановками з G будемо позначати

. Ясно, що | | = | G |. Те, що два куби До ₁ і К ₂ з М розфарбовані геометрично однаково, означає, що один з них можна перевести обертанням в таке положення, в якому вони невиразні. Іншими словами, існує така перестановка

, Що (К ₁₎ = К _2, тобто До ₁ і К ₂ містяться в одній орбіті групи

, Що діє на множині М. Таким чином, для того щоб визначити число геометрично помітних способів розмальовки вершин куба, потрібно знайти кількість орбіт групи

на безлічі М. Вважаючи вершини кубів занумеровані числами 1, 2, 3, 4, 5, 6, 7, 8, розмальовку кожного з ³ серпня кубів можна однозначно охарактеризувати «словом» з восьми літер, кожна з яких є або до, або з , або з. Те, що i-та буква слова рівна до (Або разом з, або з) означає, що i-та вершина при обраній нумерації пофарбована в червоний колір (або в синій, або в зелений відповідно). Перестановки з групи

переставляють послідовності букв до, з, з. Для того щоб застосувати лему Бернсайда, необхідно визначити число нерухомих точок кожної перестановки з

. Послідовність букв до, с, з буде нерухомою для перестановки

тоді і тільки тоді, коли при розкладанні відповідної перестановки α G у твір циклів вершини куба, номери яких входять в один і той же цикл, пофарбовані одним кольором. Якщо перестановка α G розкладена в твір k циклів, то число її нерухомих точок дорівнює 3 ^k, де

, Так як вершини куба, номери яких входять в один цикл, можна розфарбувати трьома способами. Опишемо розкладання в твір циклів для всіх перестановок з групи G обертань куба.

а) Навколо кожної з трьох осей, що з'єднують центри протилежних граней, є три обертання на кути

. Їм відповідають перестановки:
1) (1, 5, 8, 4) (2, 6, 7, 3)
2) (1, 8) (2, 7) (3, 6) (4, 5)
3) (1, 4, 8, 5) (2, 3, 7, 6)
4) (1, 4, 3, 2) (5, 8, 7, 6)
5) (1, 3) (2, 4) (5, 7) (6, 8)
6) (1, 2, 3, 4) (5, 6, 7, 8)
7) (1, 5, 6, 2) (3, 4, 8, 7)
8) (1, 6) (2, 5) (3, 8) (4, 7)
9) (1, 2, 6, 5) (3, 7, 8, 4)
б) Навколо кожної з чотирьох діагоналей куба є по два обертання. Їм відповідають перестановки:
10) (1) (2, 5, 4) (3, 6, 8) (7)
11) (2) (1, 3, 6) (4, 7, 5) (8)
12) (3) (1, 6, 8) (2, 7, 4) (5)
13) (4) (1, 3, 8) (2, 7, 5) (6)
14) (1) (2, 4, 5) (3, 8, 6) (7)
15) (2) (1, 6, 3) (4, 5, 7) (8)
16) (3) (1, 8, 6) (2, 4, 7) (5)
17) (4) (1, 8, 3) (2, 5, 7) (6)
в) Навколо кожної з шести осей, що з'єднують середини протилежних ребер куба, є одне обертання. Їм відповідають перестановки:
18) (1, 5) (2, 8) (3, 7) (4, 6)
19) (1, 2) (3, 5) (4, 6) (7, 8)
20) (1, 7) (2, 3) (4, 6) (5, 8)
21) (1, 7) (2, 6) (3, 5) (4, 8)
22) (1, 7) (2, 8) (3, 4) (5, 6)
23) (1, 4) (2, 8) (3, 5) (6, 7)
Разом з тотожною перестановкою (1) (2) (3) (4) (5) (6) (7) (8) отримуємо 24 перестановки - всі елементи групи G. Отже, у групі G обертань куба є:
1 перестановка типу <1, 1, 1, 1, 1, 1, 1, 1>,
6 перестановок типу <4, 4>,
9 перестановок типу <2, 2, 2, 2>,
8 перестановок типу <1, 1, 3, 3>.
Тоді перестановка першого типу має ³ серпня нерухомих точок, кожна з перестановок другого типу - 3 ^2, третього і четвертого типів - 3 ⁴ нерухомих точок (за формулою

_n ^k = n ^k). Тому згідно лемі Бернсайда, маємо (3 ⁸ + 6 ∙ ³ лютого + 9 ∙ 3 ⁴ + 8 ∙ 3 ⁴⁾ = 333.
Таким чином, число геометрично помітних способів розмальовки вершин куба в три кольори одно 333.
Завдання 2. Скільки різних намист із семи намистин можна скласти з намистин двох кольорів - червоного і синього?
Рішення. Переформулюємо це завдання наступним рівносильним чином: скількома геометрично різними способами можна розфарбувати вершини правильного семикутника в два кольори? Нехай М - безліч всіляких по-різному розфарбованих правильних семикутника одного розміру, положення яких в просторі фіксоване. Тоді є 2 ⁷ = 128 різних варіантів забарвлення вершин семикутника, так як кожну вершину незалежно від інших можна розфарбувати двома способами. Тут два способи розфарбування можна відрізнити, якщо один з них можна отримати з іншого, застосовуючи до семикутника або перетворення обертання, або симетрії відносно осей. Будемо описувати розмальовки «словами» довжини 7, складеними з літер к (вершина пофарбована в червоний колір) і з (вершина пофарбована в синій колір). Проробимо ті ж дії, що і в задачі 1 для застосування леми Бернсайда. Опишемо розкладання в твір циклів для всіх перестановок з групи G.
а) Тотожні перетворення відповідає перестановка:
1) (1) (2) (3) (4) (5) (6) (7)
б) повороту на кути

відповідають перестановки:
2) (1,2,3,4,5,6,7)
3) (1,3,5,7,2,4,6)
4) (1,4,7,3,6,2,5)
5) (1,5,2,6,3,7,4)
6) (1,6,4,2,7,5,3)
7) (1,7,6,5,4,3,2)
в) симетрія щодо осей, що з'єднують вершини семикутника з серединами протилежних сторін, відповідають перестановки:
8) (1) (2,7) (3,6) (4,5)
9) (2) (1,3) (7,4) (5,6)
10) (3) (2,4) (1,5) (6,7)
11) (4) (3,5) (2,6) (7,1)
12) (5) (4,6) (3,7) (2,1)
13) (6) (5,7) (4,1) (2,3)
14) (7) (1,6) (2,5) (3,4),
де 1, 2, 3, 4, 5, 6, 7 - числа, за допомогою яких занумеровані вершини семикутника.
Отже, у групі G є:
1 перестановка типу <1, 1, 1, 1, 1, 1, 1>,
6 перестановок типу <7>,
7 перестановок типу <1, 2, 2, 2>.
Слово нерухомо щодо перестановки

тоді і тільки тоді, коли літери, які стоять на місцях з номерами з одного циклу в перестановці α, збігаються. Тому тотожна перестановка має ^{7 лютого} нерухомих точок на М, перестановки другого типу - по 2, а перестановки третього типу - по 2 ^4. Застосовуючи лему Бернсайда, отримуємо
(2 ⁷ + 6 ∙ 2 + 7 ∙ 2 ⁴⁾ = 18.
Отже, з намистин двох кольорів можна скласти 18 семібусенних намист.
Завдання 3. Грані куба можна розфарбувати: а) все в білий колір, б) все в чорний колір; в) частину в білий, а інші в чорний. Скільки є різних способів розмальовки?
Рішення.

1 '

4 '

3 '

7 '

6 '

5 '

8 '

2 '

Грань (1 '4' 5 '8') - 1
Грань (2 '3' 6 '7') - 2
Грань (3 '4' 7 '8') - 3
Грань (1 '2' 5 '6') - 4
Грань (1 '2' 3 '4') - 5
Грань (5 '6' 7 '8') - 6
Рис. 3
а) Навколо кожної з трьох осей, що з'єднують центри протилежних граней, є три обертання на кути

. Їм відповідають перестановки:
1) (1) (2) (5, 4, 6, 3)
2) (1) (2) (4, 3) (6, 5)
3) (1) (2) (5, 3, 6, 4)
4) (3) (4) (1, 6, 2, 5)
5) (3) (4) (1, 2) (6, 5)
6) (3) (4) (5, 2, 6, 1)
7) (5) (6) (1, 3, 2, 4)
8) (5) (6) (1, 2) (3, 4)
9) (5) (6) (4, 2, 3, 1)
б) Навколо кожної з чотирьох діагоналей куба є по два обертання. Їм відповідають перестановки:
10) (2, 6, 3) (1, 5, 4)
11) (3, 6, 2) (4, 5, 1)
12) (6, 4, 2) (1, 5, 3)
13) (2, 4, 6) (3, 5, 1)
14) (1, 3, 6) (2, 4, 5)
15) (6, 3, 1) (5, 4, 2)
16) (1, 4, 6) (2, 3, 5)
17) (6, 4, 1) (5, 3, 2)
в) Навколо кожної з шести осей, що з'єднують середини протилежних ребер куба, є одне обертання. Їм відповідають перестановки:
18) (2, 3) (1, 4) (5, 6)
19) (1, 3) (4, 2) (5, 6)
20) (1, 6) (5, 2) (3, 4)
21) (1, 5) (6, 2) (3, 4)
22) (4, 6) (3, 5) (1, 2)
23) (6, 3) (5, 4) (1, 2)
Разом з тотожною перестановкою (1) (2) (3) (4) (5) (6) отримуємо 24 перестановки - всі елементи групи G. Отже, у групі G обертань куба є:
1 перестановка типу <1, 1, 1, 1, 1, 1>,
6 перестановок типу <1, 1, 4>,
3 перестановки типу <1, 1, 2, 2>,
8 перестановок типу <3, 3>,
6 перестановок типу <2, 2, 2>.
Тому тотожна перестановка має ^{6 лютого} нерухомих точок на М, перестановки другого і п'ятого типів мають по 2 ³ нерухомих точок на М, перестановки третього типу - по 2 ^4, а перестановки четвертого типу - за ² 2. Тоді по лемі Бернсайда отримуємо

(2 ⁶ + 6 ∙ ^{3 лютого} + 3 ∙ ^{4 лютого} + 8 ∙ ² 2 + 6 ∙ 2 ³⁾ = 10.
Отже, число геометрично різних способів розмальовки граней куба в два кольори дорівнює 10.
Завдання 4. Скільки різних намист можна скласти з двох синіх, двох білих і двох червоних намистин?
Рішення. Переформулюємо завдання так: скількома геометрично різними способами можна розфарбувати вершини правильного шестикутника так, щоб дві були синього кольору, дві - білого, дві - червоного? а) Навколо центру шестикутника є п'ять поворотів на кути

. Їм відповідають перестановки:
1) (1, 2, 3, 4, 5, 6)
2) (1, 3, 5) (2, 4, 6)
3) (1, 4) (2, 5) (3, 6)
4) (1, 5, 3) (2, 6, 4)
5) (1, 6, 5, 4, 3, 2)
б) Є три симетрії щодо осей, що з'єднують протилежні вершини правильного шестикутника. Їм відповідають перестановки:
6) (1) (4) (2, 6) (3, 5)
7) (2) (5) (3, 1) (4, 6)
8) (3) (6) (2, 4) (1, 5)
в) Є три симетрії щодо осей, що з'єднують середини протилежних сторін правильного шестикутника. Їм відповідають перестановки:
9) (1, 2) (6, 3) (5, 4)
10) (1, 6) (2, 5) (3, 4)
11) (2, 3) (1, 4) (6, 5)
Разом з тотожною перестановкою (1) (2) (3) (4) (5) (6) забезпечує 12 перестановок - всі елементи групи G. Отже, у групі G є:
1 перестановка типу <1, 1, 1, 1, 1, 1>,
2 перестановки типу <6>,
2 перестановки типу <3, 3>,
4 перестановки типу <2, 2, 2>,
3 перестановки типу <1, 1, 2, 2>.
Визначимо кількість нерухомих точок для перестановок кожного типу. Так як кількість різних кольорів, в які потрібно розфарбувати шестикутник, дорівнює трьом, то мінімальна кількість циклів в перестановці повинно бути дорівнює трьом, щоб вона мала нерухомі точки. Тобто перестановки 1), 2), 4), 5) нерухомих точок не мають. Для перестановки першого типу отримаємо

_{³ червень} =

= 90 нерухомих точок. Для кожної перестановки типу <2, 2, 2> за принципом множення отримуємо по Р ₃ = ₃ ∙ 2 ∙ 1 = 6 нерухомих точок. Для кожної перестановки типу <1, 1, 2, 2> за принципом множення отримаємо за Р ₃ = ₃ ∙ 2 ∙ 1 ∙ 1 = 6 нерухомих точок. Застосуємо лему Бернсайда:

(1 ∙ 90 + 4 ∙ 6 + 3 ∙ 6) = 11.
Отже, 11 різних намист можна скласти з двох синіх, двох білих, двох червоних намистин.
Задача 5. Скількома геометрично різними способами три абсолютно однакові мухи можуть сісти у вершинах правильного п'ятикутника?
Рішення. Позначимо М - безліч різних способів розташування трьох однакових мух в вершинах п'ятикутника, якщо вершини занумеровані. Тоді | M | =

^{₅ лютого} (3, 2) = = 10 способів розташування мух, де 2 - кількість елементів множини М ₁ = {м, з} (де м - муха, с - вільна вершина),
3, 2 - кратності відповідно м і с.
а) Навколо центру п'ятикутника є чотири повороту на кути

. Їм відповідають перестановки:
1) (1, 2, 3, 4, 5)
2) (1, 3, 5, 2, 4)
3) (1, 4, 2, 5, 3)
4) (1, 5, 4, 3, 2)
б) Є п'ять симетрій щодо осей, що з'єднують вершини п'ятикутника із серединами протилежних сторін. Їм відповідають перестановки:
5) (1) (2, 5) (3, 4)
6) (2) (1, 3) (5, 4)
7) (3) (2, 4) (1, 5)
8) (4) (3, 5) (2, 1)
9) (5) (1, 4) (2, 3),
де 1, 2, 3, 4, 5 - числа, за допомогою яких занумеровані вершини п'ятикутника. Разом з тотожною перестановкою (1) (2) (3) (4) (5) маємо 10 елементів групи G. Отже, у групі G є:
1 перестановка типу <1, 1, 1, 1, 1>,
4 перестановки типу <5>,
5 перестановок типу <1, 2, 2>.
Визначимо кількість нерухомих точок для перестановок кожного типу. Щоб перестановка мала нерухомі точки, мінімальна кількість циклів в перестановці має дорівнювати двом, так як безліч М ₁ складається з двох елементів м і с. Тому перестановки 1) - 4) не мають нерухомих точок. Тоді для перестановки типу <1, 1, 1, 1, 1> маємо за формулою:

^{₅ лютого} (3, 2) = = 10 нерухомих точок. Для кожної перестановки типу <1, 2, 2> отримаємо за принципом множення по Р ₂ = ₂ ∙ 1 ∙ 1 = 2 нерухомі точки. За лемі Бернсайда отримуємо

(1 ∙ 10 + 5 ∙ 2) = 2.
Отже, двома геометрично різними способами три однакові мухи можуть сісти у вершинах правильного п'ятикутника.
Завдання 6. Скількома способами можна розфарбувати вершини куба в два кольори (червоний і синій) так, щоб вершин кожного кольору було порівну?
Рішення. Для вирішення цього завдання скористаємося завданням 1. Нехай М - безліч всіляких по-різному розфарбованих кубів одного розміру, положення яких в просторі фіксоване. Тоді за формулою

_n ^k (K _1, k _2, ..., k _n) = отримаємо | M | =

₂ ⁸ (4,4) = = 70 по-різному розфарбованих кубів. Оскільки ми мусимо розфарбувати вершини в два кольори (4 - у червоний, 4 - у синій), то мінімальна кількість циклів в перестановці має дорівнювати двом. Тому всі перестановки 1) - 24) (завдання 1) мають нерухомі точки. В результаті в групі G є:
1 перестановка типу <1, 1, 1, 1, 1, 1, 1, 1>,
6 перестановок типу <4, 4>,
9 перестановок типу <2, 2, 2, 2>,
8 перестановок типу <1, 1, 3, 3>.
Тоді перестановка типу <1, 1, 1, 1, 1, 1, 1, 1> має

₂ ⁸ (4,4) = = 70 нерухомих точок. Кожна перестановка типу <4, 4> має (за принципом множення Р ₂ = ₂ ∙ 1 = 2 нерухомі точки. Для кожної перестановки типу <2, 2, 2, 2> є

_{² квітня} (2, 2) = = 6 нерухомих точок. Кожна перестановка типу <1, 1, 3, 3> має (за принципом множення) Р ₂ = ₂ ∙ 1 ∙ 2 ∙ 1 = 4 нерухомі точки. За лемі Бернсайда отримуємо

(1 ∙ 70 + 6 ∙ 2 + 9 ∙ 6 + 8 ∙ 4) = 7.
Отже, сім'ю способами можна розфарбувати вершини куба в два кольори так, щоб вершин кожного кольору було порівну.
Завдання 7. Скількома різними способами можна грані куба розфарбувати в чотири кольори так, щоб всі чотири кольори були присутні в розфарбовуванні кожного куба?
Рішення. Для вирішення цього завдання скористаємося завданням 3. Нехай М - безліч всіляких по-різному розфарбованих кубів одного розміру, положення яких в просторі фіксоване. Тоді за принципом множення: першу грань можна розфарбувати 4 способами, другу - трьома, третю - двома, четверту - одним способом, п'яту - чотирма, шосту - чотирма способами. Отримаємо | M | = 4 ∙ 3 ∙ 2 ∙ 1 ∙ 4 ∙ 4 = 384. Знайдемо геометрично різні способи розмальовки. Для цього використовуємо описані в задачі 3 розкладання в твір циклів всіх перестановок з групи G обертань куба. Так як в розфарбовуванні куба повинні бути присутніми чотири різні кольори, то мінімальна кількість циклів в перестановці має дорівнювати чотирьом. Тому перестановки 1), 3), 4), 6), 7), 9) - 23) в задачі 3 нерухомих точок не мають. Таким чином, нерухомі точки мають 3 перестановки типу <1, 1, 2, 2> і 1 перестановку типу <1, 1, 1, 1, 1, 1>. Визначимо кількість нерухомих точок для перестановок кожного типу. Для перестановки типу <1, 1, 1, 1, 1, 1> маємо за принципом множення Р ₄ = ₄ ∙ 3 ∙ 2 ∙ 1 ∙ 4 ∙ 4 = 384 нерухомі точки. Для кожної перестановки типу <1, 1, 2, 2> за принципом множення є Р ₄ = ₄ ∙ 3 ∙ 2 ∙ 1 = 24 нерухомі точки. За лемі Бернсайда отримуємо

(1 ∙ 384 +3 ∙ 24) = 19.
Отже, існує 19 різних способів розмальовки граней куба в 4 кольори так, щоб усі 4 кольору були присутні в розфарбовуванні кожного куба.

§ 2. «Метод просіювання» [4]

Познайомимося з найбільш загальним методом перерахунку, який можна назвати «методом просіювання» або «комбінаторним просіюванням»: з будь-яким властивістю P можна зв'язати його розщеплення на деякій множині A, відповідно до якого A розбивається на дві частини: підмножина А _1, утворене елементами, які мають властивість Р, і А _2, утворене елементами, що не володіють властивістю Р, т. е. які мають властивість

. Вибираючи властивості відповідним чином, можна послідовним просіюванням перерахувати підмножини з накладеними на них тими чи іншими обмеженнями.
2.1. Формула включення і виключення
Нехай А - кінцеве безліч і

. Будемо позначати через

додаток А ₁ по відношенню до А, а через Card A - число елементів в А.
Тоді

.
Якщо

, То

(1)

.
Покажемо, що формула (1) узагальнюється на випадок n підмножин

, I = 1, 2, ... n:

(2)
Діємо за індукції. Маємо

(3)
Припустимо, що (2) виконується для випадку n -1 підмножин A _i, i = 1, 2, ..., n -1:

(4)
Розглянемо наступні підмножини множини A _n:

Застосовуючи (4) з A = A _n, маємо

(5)
Підставляючи (5) і (4) в (3), отримуємо (2). Таким чином, з урахуванням (1) формула (2) доведена за індукції. Цю формулу називають формулою включення і виключення. Часто її представляють у такому вигляді:

(6)
Формули (2) і (6) відіграють основну роль в перерахуванні підмножин, що володіють заданими властивостями. Подивимося на ці формули з іншої точки зору. Нехай елементи

мають властивість P _i, i = 1, 2, ..., n. Тоді ми скажемо, що підмножина

має властивість

. Таким чином, якщо елементи А можуть володіти n різними властивостями, то число елементів А, які мають k зазначеними властивостями і не володіють n - k іншими, дається формулою (6).
2.2. Загальний метод «просіювання» або «пропускання через решето». Решето Сільва - Сильвестра
Формула (6) описує послідовний процес перерахунку, званий решетом Сільва - Сильвестра.
Приклад. Розглянемо безліч

і такі властивості:
парне число,
і А> 6, (7)
і 2 <A <8.
Підрахуємо кількість елементів А, що володіють властивістю

. Позначимо підмножини, відповідні властивостям Р _1, Р _2, Р _3, через А _1, А _2, А _3. Тоді

«Просіваємо» спочатку А через Р _1: Card A ₁ = 6. Потім просіваємо А ₁ через Р ₂ і Р _3:

. Просіваємо

через Р _3:

Отже,

Формула (6) не дозволяє, проте, перерахувати елементи шуканого множини. Знаходимо його, виписуючи послідовно:

. Зрозуміло, для множини з невеликим числом елементів простіше виписати шукане підмножина, проте це важко зробити при великій потужності множини.
2.3. Використання загального методу решета в теорії чисел
Теорема 1. Нехай А = {1, 2, ..., n} і а _1, а _2, ..., а _r, , I = 1, 2, ..., r, попарно взаємно прості. Кількість цілих чисел k таких, що 0 <k ≤ n, a _i не ділить k, i = 1, 2, ..., r, так само
(8)
Доказ. Позначимо

і випишемо формулу (2):

(9)
Маємо
Card A = n,
Card A _i =

, I = 1, 2, ..., r,

, I ≠ j, i, j = 1, 2, ..., r,
∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ (10)

.
Підставляючи (10) в (9), отримуємо (8).
Приклад. Нехай

, А ₁ = 3, а ₂ = 7, а ₃ = 8.
Кількість цілих чисел, що не перевищують 35 і не діляться ні на 3, ні на 7, ні на 8, так само

Розглянемо інші додатки.
Кількість цілих чисел k таких, що
0 <k ≤ n, (k, n) = 1, ,
позначають через φ (n) і називають функцією Ейлера.
Теорема 2. Нехай . Тоді
, (11)
де добуток береться по усіх простих делителям а _i числа n.
Доказ. Так як всі a _i ділять n і взаємно прості, то маємо

.
За формулою (8)

тобто отримуємо (11).
Приклад. Нехай n = 84. Простими дільниками 84 є 2, 3, 7; тому

Функція Мебіуса. Уявімо (11) в іншому вигляді, використовуючи функцію Мебіуса μ (n), яка визначається наступним чином:
μ (1) = 1;
μ (n) = 0, якщо n ділиться на квадрат простого числа;
μ (а ₁ а ₂ ... а _r) = (-1) ^r, якщо a _i - різні прості множники, i = 1, 2, ..., r.
Перетворимо рівність (11), використовуючи функцію Мебіуса:

Тоді

, (12)
де підсумовування проводиться по всіх k, що ділять n (включаючи 1).
Приклад. Маємо
μ (1) = 1,

При n = 84 формула (12) дає

Решето Ератосфена. Відомий наступний спосіб перерахування простих чисел p _i, p _i ≤ n: обчислюється

і з послідовності 2, 3, ..., n викреслюються послідовно всі числа, кратні 2, потім кратні 3, ..., кратні c. Решта числа і є шукані.
Використовуючи теорему 2, можна отримати наступну формулу перерахунку. Якщо через M (n) позначити кількість простих чисел q таких, що

, То в силу (8)
M (n) = (13)
де p _i -, i = 1, 2, ..., r, - прості числа, не перевершують

(- 1 у правій частині додається, так як 1 не вважається простим).
У силу (12)
M (n) =

, (14)
де підсумовування в (14) проводиться по всіх простим делителям n (включаючи 1).
Приклад. Скільки простих серед чисел 2, 3, ..., 84? Маємо

= 9. Простими числами між 2 і 9 будуть 2, 3, 5, 7. Згідно (13)

Таким чином, є всього 19 + 4 = 23 простих числа серед 2, 3, ..., 84. Решето Ератосфена перераховує їх: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83 .
Розширення даної теми: іноді підмножини не виділяються, а фіксується число властивостей, якими володіють їхні елементи. Для цього випадку можна вивести формулу, використовуючи формулу (6).

§ 3. Розбиття фігур на частини меншого діаметру [1, 2]

Діаметром фігури F назвемо таку відстань d, що, по-перше, відстань між будь-якими двома точками M і N фігури F не перевершує d, і, по-друге, можна відшукати в фігурі F хоча б одну пару точок A, B, відстань між якими точно дорівнює d.
Приклади:
· Якщо фігура F являє собою сегмент кола, обмежений дугою l і хордою а, то у випадку, коли дуга l не перевершує півкола, діаметр фігури F дорівнює а, у випадку ж, коли дуга l більше півкола, діаметр фігури F збігається з діаметром усього кола.
· Якщо фігура F являє собою багатокутник, то його діаметром є найбільша з відстаней між вершинами.
У фігурі може існувати і багато пар точок, відстань між якими дорівнює d: у разі еліпса така пара точок тільки одна, в разі квадрата їх дві, у разі правильного трикутника - три, у разі кола таких пар нескінченно багато.
Постановка завдання: Коло діаметра d не можна розбити на дві частини, діаметр кожної з яких буде менше d, але можна розбити на три такі частини (рис. 4 (а, б)).
ref SHAPE \ * MERGEFORMAT

Рис. 4

б)

а)

Тим же властивістю володіє рівносторонній трикутник зі стороною d. Але є фігури, які можна розбити на дві частини меншого діаметра (рис. 5 (а, б)).

ref SHAPE \ * MERGEFORMAT

Рис. 5

а)

б)

Ми можемо розглядати для будь-якої фігури F завдання про розбивку її на частини меншого діаметру. Найменше число частин, які для цього будуть потрібні, позначимо через a (F). Якщо F - коло чи рівносторонній трикутник, то a (F) = 3, а для еліпса або паралелограма a (F) = 2. Виникає питання, чи не можна знайти плоску фігуру, для якої a (F)> 3, тобто таку фігуру, що для розбивки її на частини меншого діаметру не можна обійтися трьома частинами, а буде потрібно 4 або більше число частин?
Відповідь дає т еорема Борсука: Будь-яка плоска фігура F діаметра d може бути розбита на три частини діаметра менше d, тобто a (F) ≤ 3.
Лемма: Будь-яка плоска фігура діаметра d може бути укладена в правильний шестикутник, у якого відстань між паралельними сторонами одно d.
Доказ леми.
Проведемо до фігури F опорні прямі l ₁ і l _2, причому l ₂ паралельна l _1. Вся фігура буде знаходитися в смузі між прямими l ₁ і l _2, відстань між якими не перевершує d (так як діаметр фігури F дорівнює d) (рис. 6). Проведемо до фігури F дві паралельні опорні прямі m ₁ і m _2, складові з l ₁ кут 60 °. Прямі l _1, l _2, m _1, m ₂ утворюють паралелограм ABCD з кутом 60 ° і висотами не переважаючими d, всередині якого цілком полягає фігура F. Проведемо дві опорні прямі p _1, p ₂ фігури F, складові з l ₁ кут 120 °, і позначимо через M і N підстави перпендикулярів, опущених на ці прямі з кінців діагоналі AC паралелограма (рис. 6). Покажемо, що напрямок прямий l ₁ можна вибрати таким чином, щоб виконувалося рівність AM = CN. Припустимо, AM ≠ CN, і нехай, для визначеності, AM <CN. Таким чином, величина y = AM - CN негативна. Почнемо безперервно змінювати напрямок прямий l ₁ так, щоб вона повернулася на 180 ° (фігуру F будемо залишати нерухомою). Разом з прямою l ₁ будуть змінювати своє положення прямі l _2, m _1, m _2, p _1, p ₂ (Так як їх положення визначається вибором l _1). Тому при повороті прямий l ₁ будуть безперервно переміщатися і точки A, C, M, N, а значить, буде не

Рис. 6

60 °

l ₁

l ₂

p ₂

p ₁

m ₂

m ₁

безперервно змінюватися величина y = AM - CN.
ref SHAPE \ * MERGEFORMAT

Але коли пряма l ₁ повернеться на 180 °, вона займе положення, яке раніше займала пряма l _2. Тому ми отримаємо той же паралелограм, що й на рис. 6, але в ньому точки А і С, а так само М і N поміняються «ролями». Отже, в цьому положенні величина у буде вже позитивною.
ref SHAPE \ * MERGEFORMAT

90 °

180 °

Рис. 7

Якщо ми тепер зобразимо графік зміни величини у при повороті прямий l ₁ від 0 ° до 180 ° (рис. 7), то побачимо, що знайдеться положення прямої l _1, при якому величина у звертається в нуль, тобто АМ = CN (Бо, безперервно змінюючись від негативного значення до позитивного, величина у повинна в деякий момент звернутися в нуль). Ми розглянемо стан всіх наших прямих якраз в той момент часу, коли величина у звертається в нуль (рис. 8). З рівності АМ = CN випливає, що шестикутник, утворений прямими l _1, l _2, m _1, m _2, p _1, p _2, центрально-симетричний.
ref SHAPE \ * MERGEFORMAT

60 °

l ₂

m ₂

l ₁

m ₁

p ₂

p ₁

Рис. 8

Кожен кут цього шестикутника дорівнює 120 °, а відстань між протилежними сторонами не перевершує d. Якщо відстань між p ₁ і p ₂ менше d, то ми розсунемо ці прямі (переміщаючи їх на однакову відстань) так, щоб відстань між розсунутими прямими було одно d. Точно так само ми зробимо з прямими l _1, l _2, а за тим з прямими m _1, m _2. У результаті ми отримаємо центрально-симетричний шестикутник (з кутами 120 °), у якого протилежні сторони віддалені один від одного на відстань d . Зі сказаного ясно, що всі сторони цього шестикутника рівні між собою, тобто цей шестикутник - правильний, причому фігура F розташована всередині шестикутника.

Рис. 9

Доказ теореми Борсука. Нехай F - фігура діаметра d. Згідно доказової лемі, фігура F міститься всередині правильного шестикутника, відстань між протилежними сторонами якого дорівнює d. Покажемо, що цей правильний шестикутник можна розрізати на три частини, кожна з яких має діаметр, менший d. При цьому фігура F також розріже на три частини, діаметр кожної з яких буде менше d. Необхідну розбиття правильного шестикутника на три частини показано на рис. 9 (точки P, Q і R є серединами сторін, а О - центр шестикутника). Щоб переконається, що діаметри частин менше d, достатньо зауважити, що в трикутнику PQL кут Q прямий, і тому PQ <PL = d. Таким чином, теорема доведена.
З доведення теореми легко дійти висновку, що будь-яка плоска фігура діаметра d може бути розбита на три частини, діаметр кожної з яких не перевершує (Так як PQ =

) (Рис. 9). Ця оцінка діаметрів частин є найкращою, тому що коло діаметра d не можна розбити на три частини, діаметр кожної з яких був би менше

(Частина, що має діаметр менше

, Висікає на окружності безліч, розташоване на дузі, менша 120 °, тому три такі частини не покривають всьому колу).
Можна запропонувати наступні розширення з даного питання:
Теорема Борсука є стрижнем цього питання, але вона не дає повного вирішення питання про те, чому одно a (F) для довільної заданої фігури F діаметра d. Вона дає лише оцінку a (F) зверху: a (F) ≤ 3. У той же час, очевидно, що a (F) ≥ 2 для будь-якої фігури. Виникає завдання: для яких плоских фігур a (F) дорівнює двом і для яких воно дорівнює трьом .
Можна розглядати завдання про покриття опуклих фігур гомотетічнимі (про найменшому числі «зменшених копій» фігури F, якими можна покрити всю фігуру F) і задачу про найменшому числі напрямків, які висвітлюють всю кордон фігури F.
Всі ці завдання можна розглянути для просторових тіл.

§ 4. «Щасливі квитки» [5]

Назвемо квиток щасливим, якщо сума перших трьох цифр його номера дорівнює сумі останніх трьох цифр (для шестизначних номерів). Виникає питання, скільки всього існує щасливих квитків?

Розіб'ємо всі щасливі квитки на класи, в кожному з яких сума перших трьох цифр однакова. Ця сума може набувати значення від 0 (для трійки цифр 000) до 27 (для трійки 999). Тому число класів одно 28. Позначимо через a _n число різних трійок цифр з сумою цифр n. Перші кілька значень a _n неважко обчислити:
· А ₀ = 1 (є всього одна трійка цифр 000 з сумою 0);
· А ₁ = 3 (є три трійки 001, 010, 100 з сумою цифр 1);
· А ₂ = 6 (трійки 002, 020, 200, 011, 101, 110).
Число щасливих квитків, сума перших трьох цифр яких дорівнює n, є a _n ² (як на початку, так і в кінці номера щасливого квитка можна поставити будь-яку трійку цифр із сумою n). Таким чином, для підрахунку числа щасливих квитків нам достатньо обчислити числа a _n, а потім знайти суму квадратів цих 28 чисел.
Для обчислення значень a _n порахуємо число одно-і двозначних чисел з сумою цифр n. Для кожного n = 0, 1, 2, ..., 9 існує рівно одне однозначне число з сумою цифр n (запис цього числа збігається із записом числа n). Будемо описувати однозначні числа многочленом

. Сенс у цього многочлена наступний: коефіцієнт при s ⁿ в многочлене А ₁ дорівнює числу однозначних чисел, сума цифр яких дорівнює n. Іншими словами, коефіцієнт при s ⁿ в многочлене А ₁ дорівнює 1, якщо 0 ≤ n ≤ 9, і дорівнює 0, якщо n> 9.
Випишемо многочлен А ₂ (s), що описує двозначні числа. Коефіцієнт при s ⁿ в многочлене А ₂ (s) дорівнює числу двозначних чисел з сумою цифр n. (Ми розглядаємо і такі двозначні числа, в яких перша цифра або обидві цифри можуть дорівнювати нулю). Ступінь многочлена А ₂ дорівнює 18 (це найбільша можлива сума цифр двозначного числа):

.
Пропозиція 1. А ₂ (s) = (А ₁ (s)) ^2.
Доказ. Твір моном s ^k і s ^m дає внесок у коефіцієнт при моном s ⁿ многочлена (А ₁ (s)) ² в тому і тільки в тому випадку, якщо n = k + m. Тому коефіцієнт при моном s ⁿ в многочлене (А ₁ (s)) ² є в точності число способів представити число n у вигляді суми n = k + m, k, m = 0, 1, ..., 9. Таким чином, многочлен у правій частині рівності збігається з многочленом А _2.
Випишемо многочлен

.
Пропозиція 2. А ₃ (s) = (А ₁ (s)) ^3.
Доказ. Коефіцієнт при моном s ⁿ в многочлене (А ₁ (s)) ³ дорівнює числу уявлень числа n у вигляді суми трьох цифр n = k + m + l, k, m, l = 0, 1, ..., 9 .
Отже, завдання про кількість щасливих квитків звелася до наступного: треба порахувати число р ₀ - суму квадратів коефіцієнтів многочлена (А ₁ (s)) ^3. Множення на многочлен А ₁ (s) - дуже проста операція. Але ми застосуємо апарат математичного аналізу.
Підставимо замість s вираз e ^iφ. Тоді А ₃ (e ^iφ) = (А ₁ (e ^{iφ)) 3} буде тригонометричним поліномом 27-го ступеня:

.
Скориставшись тим, що

, Отримаємо

Підсумовуючи геометричну прогресію і користуючись тим, що

,
отримуємо

, Звідки шукана величина дорівнює

. (15)
Спробуємо оцінити значення інтеграла (15). Графік функції

на відрізку

виглядає так:
ref SHAPE \ * MERGEFORMAT

0,5

1,5

-0,5

-1

-1,5

У нулі функція досягає свого максимуму, рівного 10. Поза відрізка

величина функції f не перевершує

. Тому внесок доповнення до відрізка

в інтеграл (1) не перевершує π ∙ ³ Червня ≈ 2100 (насправді він значно менше). Основна ж складова інтеграла (1) зосереджена на відрізку

. Для оцінки внеску цього відрізка скористаємося методом стаціонарної фази. Цей метод дозволяє оцінити значення інтеграла

при t → ∞. При великих значеннях t величина інтеграла визначається поведінкою функції ln f («Фази») в околиці своєї стаціонарної точки 0 (точки, в якій (ln f) '= 0, або, що те ж саме, f '= 0). В околиці нуля

, А

.
При великих t маємо

.
Вважаючи t = 6 і користуючись формулою (15), отримуємо наближене рівність

. Отриманий результат з хорошою точністю (відхилення складає не більше 3%) наближає шукане значення.
На підставі розглянутого прикладу можна зробити деякі висновки про комбінаторних задачах і методи їх вирішення. Завдання перечіслітельной комбінаторики складаються в підрахунку числа об'єктів, що належать деякому сімейства кінцевих множин. У кожного безлічі сімейства є свій номер (в задачі про щасливі квитках таким номером була сума цифр тризначного числа).
Як правило, завдання перечіслітельной комбінаторики «в принципі» розв'язна: для кожного безлічі з сімейства можна виписати всі його елементи і таким чином дізнатися їх число. Проблема полягає в тому, щоб знайти «хороше» рішення, яке не потребує виписування всіх елементів досліджуваних множин. Визначити, що таке «добре» рішення, досить важко.
При вирішенні завдань перечіслітельной комбінаторики дуже корисно розглядати виробляють многочлени. У нашому випадку користь приніс виробляє многочлен А _3. Операції з комбінаторними об'єктами дуже природно виражаються в термінах генератрис. Так, перехід від однозначних чисел із заданою сумою цифр до тризначним числах складався просто у зведенні виробляє многочлена А ₁ в куб. Залучення методів із суміжних областей математики (наприклад, з аналізу) дозволяє по-іншому поглянути на перечіслітельной завдання і знайти нові, часто несподівані, підходи до її вирішення.

Бібліографічний список

1. Болтянский, В.Г. Теореми і задачі комбінаторної геометрії [Текст] / В.Г. Болтянский, І.Ц. Гохберг / / - М.: Наука, 1965.
2. Болтянский, В.Г. Розбиття фігур на менші частини [Текст] / В.Г. Болтянский, І.Ц. Гохберг / / - М.: Наука, 1971.
3. Калужнін, Л.А. Перетворення і перестановки [Текст] / Л.А. Калужнін, В.І. Сущанський / / - М.: Наука, 1979.
4. Кофман, О. Розвиток методів перерахунку [Текст] / А. Кофман / / Введення в прикладну комбінаторику - М.: Наука, 1975. - С. 60-73.
5. Ландо, С.К. Щасливі квитки [Текст] / / Математичне просвітництво, сер. 3, вип. 2. - М.: Просвещение, 1998. - С. 127-132.

Зв`язок комбінаторики з різними розділами математики